#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    const int INF=1e9 + 7;
    int numberOfWays(int n, int x) {
        int l=1;
        for(int i=l;;i++)
        {
            if(pow(i,x)>=n)
            {
                l=i;
                break;
            }
        }
        vector<vector<int>> dp(l+1,vector<int>(n+1));
        for(int i=0;i<=l;i++) dp[i][0]=1; 
        for(int i=1;i<=l;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=dp[i-1][j];
                int k=pow(i,x);
                if(j==k||(j>k&&dp[i-1][j-k]!=0)) dp[i][j]+=dp[i-1][j-k];
                dp[i][j]%=INF;
                
            }
        }
        return dp[l][n];
    }
};
int main()
{
    int n=10;
    int x=2;
    Solution so;
    so.numberOfWays(n,x);
    return 0;
}